% !TEX root = disc2012.tex

\section{Network Model and Definitions}\label{sec:model}
\vspace{-0.1in}
\subsection{Dynamic Networks}
\vspace{-0.03in}
We study a general model to describe a dynamic network with a {\em fixed} set of nodes. We consider an oblivious adversary which can make {\em arbitrary} changes to the graph topology in every round as long as the graph is {\em connected}. Such a dynamic graph process (or dynamic graph, for short) is also known as an {\em Evolving Graph} \cite{AKL08}. Suppose $V = \{v_1, v_2, \ldots,v_n\}$ be the set of nodes (vertices) and $\mathcal{G} = G_1, G_2, \ldots$ be an infinite sequence of undirected (connected) graphs on $V$. We write $G_t = (V, E_t)$ where $E_t \in 2^{V\times V} $ is the dynamic edge set corresponding  to round $t \in \mathbb{N}$. The adversary has complete control on the topology of the graph at each round, however it does not know the random choices made by the  algorithm.
In particular, in the context of random walks,  we assume that it does not know the position of the random walk in any round (however, the adversary may know the starting position).\footnote{Indeed, an adaptive adversary that always knows the current position of the random walk can easily choose graphs in each step, so that the walk never really progresses to all nodes in the network.}    Equivalently, we can assume that the adversary chooses the entire sequence $\langle G_t \rangle$ of the graph process $\mathcal{G}$ in advance before execution of the algorithm. This adversarial model has also been used  in \cite{AKL08} in their study of random walks in dynamic networks. 

We say that the dynamic graph process $\mathcal{G}$ has some property when each $G_t$ has that property. 
%This model captures most interesting scenarios of dynamic networks, but most natural problems are NP-complete such as finding strongly connected components and the equivalence of minimum spanning tree~\cite{Feria04, AKL08}. 
For technical reasons, we will assume that each graph $G_t$ is  $d$-regular and  non-bipartite. 
%This ensures  % since in a non-regular dynamic graph it is easy for an oblivious adversary (that knows the starting position)
%to make sure that the walk does not progress.\footnote{For example, consider a line with the walk starting at the first vertex (one end),
%and the first and second vertices are interchanged in every round. However, in a }
%that the random walk will make progress and visit every vertex \cite{AKL08}, and in particular, will ``mix" well (cf. Section \ref{sec:rwd} and  Theorem~\ref{thm:mixtime} in the Appendix).  
Later we will show that our results can be generalized to apply to non-regular graphs as well (albeit at the cost
of a slower running time). The assumption on non-bipartiteness ensures that the mixing time is well defined, however this restriction can be removed using a standard technique: adding self-loops on each vertices (e.g., see \cite{AKL08}). 
Henceforth, we assume that the dynamic graph is a {\em $d$-regular evolving graph}  unless otherwise stated (these two terms will be used interchangeably).  Also we will assume that each $G_t$ is non-bipartite (and connected).

%The work of \cite{AKL08} showed that there are evolving graphs in which a simple random walk takes exponential time to visit all the nodes.  However this is not possible if the evolving graph is regular, see in \cite{AKL08}.  in Theorem~\ref{thm:mixtime} (Section~\ref{mixing_time} in appendix) that after a finite number of step of a simple random walk in a regular evolving graph, the distribution on the vertex set becomes close to the uniform distribution.  \\ %We call it {\em Stationary Evolving Graph} defined below. 
%\footnote{This terminology is similar to the stationarity assumption in information theory, where a stationary stochastic process is one whose entropy is  well-defined and fixed.} 
%({\bf Anisur:} I am removing the definition of stationary evolving graph. There will be no stationary evolving graph, only evolving graph. Also I include the part why we need regularity assumption)

\iffalse
\begin{definition}
A {\em stationary evolving graph} is a dynamic graph $\mathcal{G} = G_1, G_2, \ldots$ where each graph $G_t$ has the same spectral properties including the same eigenvalues and mixing time. In particular, each graph $G_t$ has the same spectral gap i.e. the same second largest eigenvalue ($\lambda_2$) of the transition matrix.  %he mixing time ($\tau_{mix}$) of all the graphs $G_t$ varies at most within $\log n$ factor as it is known that $\frac{1}{1-\lambda_2}\leq \tau_{mix}\leq \frac{\log n}{1-\lambda_2}$~\cite{JS89}. 
\end{definition}
\fi
%{\bf anisur:} I changed below.
%\noindent

 
%, at the cost of some loss in performance.
%We will also assume that each $G_t$ is non-bipartite, which ensures that the mixing time is well-defined (however, this assumption can be easily removed by considering a lazy random walk e.g., \cite{AKL08}).

\vspace{-0.15in}
\subsection{Distributed Computing Model}
\label{sec:distmodel}
%\vspace{-0.1in}
We model the communication network as an $n$-node dynamic graph process $\mathcal{G} = G_1, G_2, \ldots$. Every  node has limited initial knowledge. Specifically, assume that each node is associated with a distinct identity number (ID). (The node ids are of size $O(\log n)$.) At the beginning of the computation, each node $v$ accepts as input its own identity number and the identity numbers of its neighbors in $G_1$. The node may also accept some additional inputs as specified by the problem at hand (in particular, we assume that all nodes know $n$). The nodes are allowed to communicate through the edges of the graph $G_t$  in each round $t$. We assume that the communication occurs in  synchronous  {\em rounds}. 
In particular, all the nodes wake up simultaneously at the beginning of round $1$, and from this point on the nodes always know the number of the current round. 
We will use only small-sized messages. In particular, at the beginning of each round $t$, each node $v$ is allowed to send a message of size $B$ bits (typically $B$ is assumed to be $O(\polylog n)$) through each edge $e = (v, u) \in E_t$ that is adjacent to $v$.  The message  will arrive to $u$ at the end of the current round. 
This is a standard model of distributed computation known as the {\em CONGEST(B) model} \cite{peleg,PK09} and has been attracting a lot of research attention during last two decades (e.g., see \cite{peleg} and the references therein).
 %Our algorithms can be easily generalized if $B$ bits  are allowed (for any pre-specified parameter $B$) to be sent through each edge in a round. Typically, as assumed here, $B = O(\log n)$, which is number of bits needed to send a node id in an n-node network.
 %Gopal: This congest $\log^2 n$ should be write more carefully. 
 %Anisur: I include the part why we need congest $\log^2 n$ model. Please check it. 
For the sake of simplifying our analysis, we assume that $B = O(\log^2 n)$, although this is generalizable.\footnote{It turns out that the per-round congestion in any edge  in our random walk algorithm is $O(\log^2 n)$ bits  w.h.p.  Hence assuming this bound for $B$ ensures that the random walks can never be delayed due to congestion. This simplifies the correctness proof of our random walk algorithm (cf. Lemma \ref{lem:correctness}).} 
%Congestion can affect  moving the walk at $t$-th step in the graph $G_t$. So considering {\em CONGEST$(\log^2 n)$ model} ensures that there will be no congestion in our algorithm and each walk can extend their length from $t$ to $t+1$ in the graph $G_t$. We refer to the reader to look on the correctness of our algorithm for more explicit discussion on this.  

There are several measures of efficiency of distributed algorithms,
but we will focus on one of them, specifically, {\em the
running time}, i.e. the number of {\em rounds} of distributed
communication. (Note that the computation that is performed by the
nodes locally is ``free'', i.e., it does not affect the number of
rounds.)
%This work addresses the
%problem of computing random walks in a time-efficient manner.
\vspace{-0.15in}
\subsection{Random Walks in a Dynamic Graph}
\label{sec:rwd}
\vspace{-0.05in}
Throughout, we assume the {\em simple   random walk} in an undirected graph: In each step, the walk goes from the current node to a random neighbor, i.e., from the current node $v$, the probability to move in the next step to a neighbor $u$ is $\Pr(v,u) = 1/d(v)$  for $(v,u) \in E$ and $0$ otherwise  ($d(v)$ is the degree of $v$).

A {\em simple random walk} on dynamic graph $\mathcal{G}$ is defined as follows: assume that at time $t$ the walker is at node $v \in V$, and let $N(v)$ be the set of neighbors of $v$ in $G_t$, then the walker goes to one of its neighbors from $N(v)$ uniformly at random.  
%Gopal --- Define formally mixing time and dynamic mixing time in the Appendix and reference it below.

%Suppose we have a random walk $v_0 \rightarrow v_1 \rightarrow \ldots \rightarrow v_t$ on a dynamic graph $\mathcal{G}$, where $v_0$ is the starting vertex. Then we get a probability distribution $P_t$ on $v_t$ starting from the initial distribution $P_0$ on $v_0$. 
Let $\pi_x(t)$ define the probability distribution vector reached after $t$ steps when the initial distribution starts with probability $1$ at node $x$. 
We say that the distribution $\pi_x(r)$ is stationary (or steady-state) for the graph process $\mathcal{G}$ if $\pi_x(t+1) = \pi_x(t)$ for all $t \ge r$. Let $\pi$ denote the stationary distribution vector. It is known that for every (undirected) static graph $G$, the distribution $\pi(v) = d(v)/2m$ is stationary. In particular, for a regular graph the stationary distribution is the uniform distribution.
The {\em mixing time} of a random walk on a static graph $G$ is the time $t$ taken to reach ``close'' to the stationary distribution of the graph. Similar to the static case, for a $d$-regular evolving graph, it is easy to verify that the stationary distribution is the uniform distribution.  Also, for a $d$-regular evolving graph,  the notion of {\em dynamic mixing time} (formally defined below) is similar to the static case  and is well defined due to the monotonicity property of distributions ($||\pi_x(t+1) - \pi|| \leq  ||\pi_x(t) - \pi||$, see full paper \cite{SMP12}). %\footnote{For lack of space, we place the pseudocode of  our algorithms, their analysis, and full proofs in the Appendix.}.
\begin{definition}\label{def:mix-dynamic}[Dynamic mixing time]
Define $\tau^x(\epsilon)$ ($\epsilon$-near mixing time for source $x$) is $\tau^x(\epsilon) = \min t : ||\pi_x(t) - \pi|| < \epsilon$. Note that $\pi_x(t)$ is the probability distribution on the graph $G_t$ in the dynamic graph process $\{ G_t : t\geq 1\}$ when the initial distribution ($\pi_x(1)$) starts with probability $1$ at node $x$ on $G_1$. Define $\tau^x_{mix}$ (mixing time for source $x$) $ = \tau^x(1/2e)$ and $\tau_{mix} = \max_{x} \tau^x_{mix}$. The dynamic mixing time is upper bounded by   $\tau = \max \{$mixing time of all the static graph $G_t : t \geq 1\}$. Notice that $\tau \geq \tau_{mix}$ in general. 
\end{definition} 
We show the following theorem (proof is in the full version of the paper \cite{SMP12}) of dynamic mixing time. 
\begin{theorem}\label{thm:mixtime}
For any $d$-regular connected non-bipartite evolving graph $\mathcal{G}$, the dynamic mixing time of a simple random walk on $\mathcal{G}$ is bounded by $O(\frac{1}{1- {\lambda}}\log n)$, where $\lambda$ is an upper bound of the second largest eigenvalue in absolute value of any graph in $\mathcal{G}$. Further, it is bounded by $O(n^2 \log n)$.
\end{theorem}  

%We show (cf. Theorem~\ref{thm:mixtime}) that the dynamic mixing time is  bounded by $O(\frac{1}{1-\lambda}\log n)$ rounds, where $\lambda$ is an upper bound of the second largest eigenvalue in absolute value of any graph in $\mathcal{G}$.  Note that $O(\frac{1}{1-\lambda}\log n)$ is also an upper bound on the mixing time of the graph having $\lambda$ as its second largest eigenvalue and hence 
Note that the dynamic mixing time is upper bounded by the worst-case mixing time of any graph in $\mathcal{G}$, which will be (henceforth) denoted by  $\tau$.  
Since the second eigenvalue of the transition matrix of any regular graph is bounded by $1-1/n^2$, this implies that $\tau$ of a $d$-regular evolving graph is bounded by $\tilde{O}(n^2)$. 
In general, the dynamic mixing time can be significantly smaller than this bound, e.g., when all graphs in $\mathcal{G}$ have $\lambda$ bounded from above by a constant (i.e.,  they are expanders ---  such dynamic graphs occur in applications e.g., \cite{JGPE:soda12,Kuhn-stoc}), the dynamic mixing time is $O(\log n)$. 

Another parameter affecting the efficiency of distributed computation in a dynamic graph is its dynamic diameter (also called flooding time, e.g., see~\cite{BCF09,CMMPS08}).  
The {\em dynamic diameter} (denoted by $\Phi$) of an $n$-node dynamic graph $\mathcal{G}$ is the worst-case time (number of rounds) required to broadcast a piece
of information from any given node to all $n$-nodes. 
The dynamic diameter  can be much larger than the diameter ($D$) of any (individual) graph $G_t$.

